#!/usr/bin/env python
# -*- encoding: utf-8 -*-
"""
@File        :   34. 在排序数组中查找元素的第一个和最后一个位置.py    
@Contact     :   lhouctcs@163.com
@License     :   MIT
@Time        :   2023/2/1 13:21
@Author      :   lhou 
@Version     :   0.1.0
@Description :
"""
from typing import List


# import lib
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def binarySearchLeft(nums: List[int], target: int) -> int:
            l = -1
            r = len(nums)
            while l + 1 != r:
                mid = l + (r - l) // 2
                if nums[mid] >= target:
                    r = mid
                else:
                    l = mid
            return r

        def binarySearchRight(nums: List[int], target: int) -> int:
            l = -1
            r = len(nums)
            while l + 1 != r:
                mid = l + (r - l) // 2
                if nums[mid] <= target:
                    l = mid
                else:
                    r = mid
            return l

        leftIdx = binarySearchLeft(nums, target)
        rightIdx = binarySearchRight(nums, target)

        if leftIdx <= rightIdx < len(nums) and nums[leftIdx] == target and nums[rightIdx] == target:
            return [leftIdx, rightIdx]

        return [-1, -1]


Solution().searchRange([5, 7, 7, 8, 8, 10], 8)
